#include "errhandle.h"
#include "common.h"
#include <stdlib.h>

#define FRONTIER_INITIAL_SIZE (50)

struct frontier_data
{
  mrr_byte_t *storage;
  size_t length;
  size_t head;
  size_t tail;
};

typedef struct frontier_data * frontier_t;

frontier_t
frontier_new()
{
  frontier_t frnt;

  int size = FRONTIER_INITIAL_SIZE * sizeof(int);
  frnt->storage = malloc(size);
  if (frnt->storage == NULL)
    {
      fatal("out of memory!");
    }
  frnt->length = size;
}

void
frontier_append(frontier_t frnt, int elem)
{
  size_t head, tail;
  tail = (head < tail) ? tail : tail + frnt->length;
  if (tail - head >= frnt->length)
    {
      // enlarge the frontier.
    }

  tail++;
  tail %= frnt->length;

  *(frnt->storage + tail) = elem;

  frnt->tail = tail;
}

void
frontier_cancel(frontier_t frnt, int* elems, int count)
{
  /*
   * TO BE OPTIMIZED: It's not scalable.
   *    The size of frontier may be very large, but size of elements is small. 
   */

  int *p;
  size_t q;

  p = elems + count - 1;
  q = frnt->tail;

  while (1)
    {
      int *ptr;
      ptr = frnt->storage + q * sizeof(int);

      if (*ptr == *p)
        {
          *ptr = 0;

          // next the element to cancel
          p--;
          if (p < elems)
            break;
        }

      q--;
      if (q < 0)
        q = frnt->length; // turn backward cyclically
      if (q == frnt->head)
        break; // search completely
    }
}

void
frontier_cleanup(frontier_t frnt)
{

}
